// 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

// 暴露接口
function maxSlidingWindow(nums: number[], k: number): number[] {
    // 边界情况处理
    if(nums.length<1){
        return [];
    }
    const res:Array<number> = [];// 结果数组
    const deque:Array<number> = [];// 单调递减双向队列
    // 初始化情况-->窗口未形成
    for(let i = 0;i<0+k-1;i++){
        _keepQueueDown(deque,nums[i]);// 保持队列单调性
        deque.push(nums[i]);
    }
    // 窗口形成后
    for(let i = 0+k-1;i<nums.length;i++){
        if(deque[0]===nums[i-k]) deque.shift();// 重要！判断队首元素是否过期
        _keepQueueDown(deque,nums[i]);
        deque.push(nums[i]);
        res.push(deque[0]);
    }
    return res;
};
// 保持队列的单调递减性
function _keepQueueDown(deque:number[],value:number){
    // 判断队尾元素在新进元素下是否满足单调递减
    while(deque.length>=1&&value>deque[deque.length-1]){
        deque.pop();
    }
}

// 这道题目虽然表面讲的是一道滑动窗口最大值的题目
// 但实际上考察的知识点和滑动窗口算法关系并不大
// 主要需要使用的是数据结构是双向单调队列（递减）
// 双向单调队列的作用有：
// 1、单调队列，想要的最值数据直接从队头/队尾取即可
// 2、两头可控，新数据若大于队尾数据可不断出栈实现单调
// 3、两头可控，若发现队头数据已经过旧可直接出队
// 4、本身是一种数据结构，可以有效地实现对数据的存储与管理
// 具体的详细操作可以分为形成滑动窗口前与形成滑动窗口后
// 形成滑动窗口前的操作就是逐一加入现有的元素形成单调队列
// 形成滑动窗口后，在每一轮次的循环中，首先需要判断当前的队首元素是否过期，这非常重要
// 如果过期需要先让队首元素出队
// 之后的操作是仍然需要保持队列的单调性
// 只不过在形成滑动窗口后，在每一轮次的循环结束之后可以把队首元素（最大的元素）记录在结果数组中
// 遍历结束后返回结果数组即可。



